package middle;

import java.util.HashMap;
import java.util.Map;

/**
 * 如果序列X_1, X_2, ..., X_n满足下列条件，就说它是斐波那契式的：
 *
 * n >= 3
 * 对于所有i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
 * 给定一个严格递增的正整数数组形成序列 arr，找到 arr中最长的斐波那契式的子序列的长度。如果一个不存在，返回0 。
 *
 * （回想一下，子序列是从原序列 arr中派生出来的，它从 arr中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。
 * 例如，[3, 5, 8]是[3, 4, 5, 6, 7, 8]的一个子序列）
 *
 *
 * 示例 1：
 *
 * 输入: arr = [1,2,3,4,5,6,7,8]
 * 输出: 5
 * 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
 *
 * 链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class LengthOfLongestFibonacciSubsequence {
    /**
     * 参考题解中的hash表+动态规划法，从后往前搜索
     * https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/solution/zui-chang-de-fei-bo-na-qi-zi-xu-lie-de-c-c4dt/
     * */
    class Solution {
        public int lenLongestFibSubseq(int[] arr) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                map.put(arr[i], i);
            }
            /**
             * 定义一个dp数组。dp[j][i] 表示数组中，以下标j和i结尾的斐波那契数列的长度
             * 按照如下定义，k < j < i 且 A[k] + A[j] = A[i],其中A为给定的数组
             * 则可以得出A[i] - A[j] = A[k]
             */
            int[][] dp = new int[arr.length][arr.length];

            /**
             * 初始化dp数组，所有元素的值都为2
             * */
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < dp.length; j++) {
                    dp[i][j] = 2;
                }
            }

            /**
             * 动态转移方程，i和j结尾的斐波那契数列 肯定 是基于 j 和 k结尾的斐波那契数列组成的
             * dp[j][i] = dp[k][j] + 1
             * */
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                // ps:这个循环的初始值 和 终止条件
                for (int j = i-1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
                    int k = map.getOrDefault(arr[i] - arr[j], -1);
                    if (k != -1) {
                        dp[j][i] = dp[k][j] + 1;
                    }
                    ans = Math.max(ans, dp[j][i]);
                }
            }
            // ps: 因为ans为2时，说明就没有找到匹配的斐波那契数列，所以长度应该为0
            return ans > 2 ? ans : 0;
        }
    }
}
